package com.sheng.leetcode.year2024.month07.day22;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2024/7/22
 * <p>
 * 2101. 引爆最多的炸弹<p>
 * <p>
 * 给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。<p>
 * 炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。<p>
 * 你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。<p>
 * 给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。<p>
 * <p>
 * 示例 1：<p>
 * 输入：bombs = [[2,1,3],[6,1,4]]<p>
 * 输出：2<p>
 * 解释：<p>
 * 上图展示了 2 个炸弹的位置和爆炸范围。<p>
 * 如果我们引爆左边的炸弹，右边的炸弹不会被影响。<p>
 * 但如果我们引爆右边的炸弹，两个炸弹都会爆炸。<p>
 * 所以最多能引爆的炸弹数目是 max(1, 2) = 2 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：bombs = [[1,1,5],[10,10,5]]<p>
 * 输出：1<p>
 * 解释：<p>
 * 引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]<p>
 * 输出：5<p>
 * 解释：<p>
 * 最佳引爆炸弹为炸弹 0 ，因为：<p>
 * - 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。<p>
 * - 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。<p>
 * - 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。<p>
 * 所以总共有 5 个炸弹被引爆。<p>
 * <p>
 * 提示：<p>
 * 1 <= bombs.length <= 100<p>
 * bombs[i].length == 3<p>
 * 1 <= xi, yi, ri <= 10^5<p>
 */
public class LeetCode2101 {

    @Test
    public void test01() {
//        int[][] bombs = {{2, 1, 3}, {6, 1, 4}};
//        int[][] bombs = {{1, 1, 5}, {10, 10, 5}};
//        int[][] bombs = {{1, 2, 3}, {2, 3, 1}, {3, 4, 2}, {4, 5, 3}, {5, 6, 4}};
        int[][] bombs = {{1, 1, 100000}, {100000, 100000, 1}};
        System.out.println(new Solution().maximumDetonation(bombs));
    }
}

class Solution {
    public int maximumDetonation(int[][] bombs) {
        // bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径
        int length = bombs.length;
        // 能引爆，代表两个炸弹之间的距离小于等于爆炸半价最大的炸弹
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
            for (int j = 0; j < length; j++) {
                long xj = xi - bombs[j][0], yj = yi - bombs[j][1];
                // 判断 i 位置的炸弹是否可以引爆 j 位置的炸弹
                if (i != j && xj * xj + yj * yj <= ri * ri) {
                    // i 可以引爆 j
                    List<Integer> orDefault = map.getOrDefault(i, new ArrayList<>());
                    orDefault.add(j);
                    map.put(i, orDefault);
                }
            }
        }
        // 计算引爆数量最多的炸弹
        int max = 0;
        boolean[] booleans = new boolean[length];
        for (int i = 0; i < length; i++) {
            // 防止重复引爆，进行计算
            Arrays.fill(booleans, false);
            max = Math.max(max, dfs(booleans, i, map));
        }
        return max;
    }

    public int dfs(boolean[] booleans, int i, Map<Integer, List<Integer>> map) {
        booleans[i] = true;
        int ans = 1;
        List<Integer> orDefault = map.getOrDefault(i, new ArrayList<>());
        for (Integer integer : orDefault) {
            if (!booleans[integer]) {
                ans += dfs(booleans, integer, map);
            }
        }
        return ans;
    }
}
